#include <unordered_map>
#include <iostream>

using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val)
    {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution
{
public:
    // 思路：通过哈希表映射新旧节点，然后再根据映射关系设置新节点的next和random指针
    Node *copyRandomList(Node *head)
    {
        unordered_map<Node *, Node *> oldMapNew; // 老节点到新节点的映射
        Node *cur = head;
        // 1. 创建新节点，并建立映射
        while (cur)
        {
            Node *newnode = new Node(cur->val); // 当前老节点对应的新节点
            oldMapNew[cur] = newnode;           // 建立映射
            cur = cur->next;
        }
        // 2. 设置新节点的next和random指针
        cur = head;
        while (cur)
        {
            Node *newNode = oldMapNew[cur];           // 当前老节点对应的新节点
            newNode->next = oldMapNew[cur->next];     // 设置next指针
            newNode->random = oldMapNew[cur->random]; // 设置random指针
            cur = cur->next;
        }
        return oldMapNew[head];
    }
};